import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: 二叉树1
 * User: mac
 * Date: 2022-09-23
 * Time: 11:36
 */
class TreeNode1 {
    int val;
    TreeNode1 left;
    TreeNode1 right;
    TreeNode1() {}
    TreeNode1(int val) { this.val = val; }
    TreeNode1(int val, TreeNode1 left, TreeNode1 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class TreeNode {
    public char val;
    public TreeNode left;//左孩子的引用
    public TreeNode right;//右孩子的引用

    public TreeNode(char val) {
        this.val = val;
    }

}
public class BinaryTree {
    public TreeNode root;//二叉树的根节点

    public TreeNode createTree() {//暂时写法
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //二叉树的遍历，重点: 所有二叉树相关的题目，基本上都是需要通过某种遍历取解题的
    //1.前序遍历 2.中序遍历 3.后序遍历 4.层序遍历

    //1.前序遍历 根 -> 左子树 -> 右子树 ABDCEF

    //2.中序遍历 左子树 -> 跟 -> 右子树 DBAECF

    //3.后序遍历 左子树 -> 右子树 -> 根 DBEFCA

    //练习：前序：ABDEHCFG 中序：DBEHAFCG 后序：DHEBFGCA

    //二叉树的题天生就用递归来写的

    //知道前序和后序无法确定一颗二叉树

    //前序遍历
    void preOrder(TreeNode root) {//传入二叉树的根
        if (root == null){//判断根是否为空
            return;
        }
        System.out.print(root.val + " ");//打印节点信息
        preOrder(root.left);//递归遍历该根节点的左子树
        preOrder(root.right);//递归遍历该根节点的右子树
    }

    //中序遍历
    void inOrder(TreeNode root){//传入二叉树的根
        if (root == null){//判断根是否为空
            return;
        }
        inOrder(root.left);//递归遍历该根节点的左子树
        System.out.print(root.val + " ");//中序打印根节点
        inOrder(root.right);//递归遍历该根节点的右子树
    }

    //后序遍历
    void postOrder(TreeNode root){//传入二叉树的根
        if (root == null){//判断根是否为空
            return;
        }
        postOrder(root.left);//递归遍历该根节点的左子树
        postOrder(root.right);//递归遍历该根节点的右子树
        System.out.print(root.val + " ");//后序打印根节点
    }

    public List<Integer> preorderTraversal(TreeNode1 root) {
        List<Integer> list = new ArrayList<>();

        if (root == null){
            return list;
        }
        list.add(root.val);
        list.addAll(preorderTraversal(root.left));
        list.addAll(preorderTraversal(root.right));
        return list;
    }
}
